use std::time::Instant;

// 实现冒泡排序 (O(n²))
fn bubble_sort(data: &mut [i32]) {
    let len = data.len();
    for i in 0..len {
        for j in 0..len - i - 1 {
            if data[j] > data[j + 1] {
                data.swap(j, j + 1);
            }
        }
    }
}

// 实现快速排序 (O(n log n))
fn quick_sort(data: &mut [i32]) {
    if data.len() <= 1 {
        return;
    }
    let pivot = data[data.len() / 2];
    let (mut left, mut right) = (0, data.len() - 1);
    while left <= right {
        while data[left] < pivot {
            left += 1;
        }
        while data[right] > pivot {
            right -= 1;
        }
        if left <= right {
            data.swap(left, right);
            left += 1;
            right -= 1;
        }
    }
    if right > 0 {
        quick_sort(&mut data[0..=right]);
    }
    if left < data.len() {
        quick_sort(&mut data[left..]);
    }
}

// 学生需在此函数实现两种算法并比较耗时  
fn compare_algorithms(data: &[i32]) -> (u128, u128) {  
    // TODO: 实现 O(n²) 和 O(n log n) 排序  

    // 测试冒泡排序
    let mut bubble_data = data.to_vec();
    let start = Instant::now();
    bubble_sort(&mut bubble_data);
    let time1 = start.elapsed().as_micros();

    // 测试快速排序
    let mut quick_data = data.to_vec();
    let start = Instant::now();
    quick_sort(&mut quick_data);
    let time2 = start.elapsed().as_micros();

    // 验证排序正确性（可选）
    assert!(bubble_data.windows(2).all(|w| w[0] <= w[1]));
    assert!(quick_data.windows(2).all(|w| w[0] <= w[1]));

    (time1, time2)
    //(0, 0)  
}  

#[test]  
fn test_performance() {  
    let data = (1..=1000).rev().collect::<Vec<_>>();  
    let (time1, time2) = compare_algorithms(&data);  
    assert!(time2 < time1, // 验证高效算法更快  
        "QuickSort({}μs) should be faster than BubbleSort({}μs)", time2, time1);
}  

// 添加main函数
fn main() {
    let data = vec![5, 3, 2, 4, 1];
    let (t1, t2) = compare_algorithms(&data);
    println!("BubbleSort: {}μs, QuickSort: {}μs", t1, t2);
}